Compare version numbers

Time: O(N); Space: O(1); easy

Compare two version numbers version1 and version2.

• If version1 > version2 return 1;

• if version1 < version2 return -1;

• otherwise return 0.

You may assume that the version strings are non-empty and contain only digits and the . character.

The . character does not represent a decimal point and is used to separate number sequences.

For instance, 2.5 is not “two and a half” or “half way to version three”, it is the fifth second-level revision of the second first-level revision.

You may assume the default revision number for each level of a version number to be 0.

For example, version number 3.4 has a revision number of 3 and 4 for its first and second level revision number. Its third and fourth level revision number are both 0.

Example 1:

Input: version1 = “0.1”, version2 = “1.1”

Output: -1

Example 2:

Input: version1 = “1.0.1”, version2 = “1”

Output: 1

Example 3:

Input: version1 = “7.5.2.4”, version2 = “7.5.3”

Output: -1

Example 4:

Input: version1 = “1.01”, version2 = “1.001”

Output: 0

Explanation:

• Ignoring leading zeroes, both “01” and “001” represent the same number “1”

Example 5:

Input: version1 = “1.0”, version2 = “1.0.0”

Output: 0

Explanation:

• The first version number does not have a third level revision number, which means its third level revision number is default to “0”

Notes:

• Version strings are composed of numeric strings separated by dots . and this numeric strings may have leading zeroes.

• Version strings do not start or end with dots, and they will not be two consecutive dots.

class Solution1(object):
    """
    Time: O(N)
    Space: O(1)
    """
    def compareVersion(self, version1, version2):
        """
        :type version1: str
        :type version2: str
        :rtype: int
        """
        n1, n2 = len(version1), len(version2)
        i, j = 0, 0
        while i < n1 or j < n2:
            v1, v2 = 0, 0
            while i < n1 and version1[i] != '.':
                v1 = v1 * 10 + int(version1[i])
                i += 1
            while j < n2 and version2[j] != '.':
                v2 = v2 * 10 + int(version2[j])
                j += 1
            if v1 != v2:
                return 1 if v1 > v2 else -1
            i += 1
            j += 1

        return 0

s = Solution1()
version1 = "0.1"
version2 = "1.1"
assert s.compareVersion(version1, version2) == -1
version1 = "1.0.1"
version2 = "1"
assert s.compareVersion(version1, version2) == 1
version1 = "7.5.2.4"
version2 = "7.5.3"
assert s.compareVersion(version1, version2) ==-1
version1 = "1.01"
version2 = "1.001"
assert s.compareVersion(version1, version2) == 0
version1 = "1.0"
version2 = "1.0.0"
assert s.compareVersion(version1, version2) == 0

class Solution2(object):
    """
    Time: O(N)
    Space: O(N)
    """
    def compareVersion(self, version1, version2):
        """
        :type version1: str
        :type version2: str
        :rtype: int
        """
        v1, v2 = version1.split("."), version2.split(".")

        if len(v1) > len(v2):
            v2 += ['0' for _ in range(len(v1) - len(v2))]
        elif len(v1) < len(v2):
            v1 += ['0' for _ in range(len(v2) - len(v1))]

        i = 0
        while i < len(v1):
            if int(v1[i]) > int(v2[i]):
                return 1
            elif int(v1[i]) < int(v2[i]):
                return -1
            else:
                i += 1

        return 0

s = Solution2()
version1 = "0.1"
version2 = "1.1"
assert s.compareVersion(version1, version2) == -1
version1 = "1.0.1"
version2 = "1"
assert s.compareVersion(version1, version2) == 1
version1 = "7.5.2.4"
version2 = "7.5.3"
assert s.compareVersion(version1, version2) ==-1
version1 = "1.01"
version2 = "1.001"
assert s.compareVersion(version1, version2) == 0
version1 = "1.0"
version2 = "1.0.0"
assert s.compareVersion(version1, version2) == 0

class Solution3(object):
    """
    Time: O(N)
    Space: O(N)
    """
    def compareVersion(self, version1, version2):
        """
        :type version1: str
        :type version2: str
        :rtype: int
        """
        v1 = [int(x) for x in version1.split('.')]
        v2 = [int(x) for x in version2.split('.')]
        while len(v1) != len(v2):
            if len(v1) > len(v2):
                v2.append(0)
            else:
                v1.append(0)
        return (v1 > v2) - (v1 < v2)

s = Solution3()
version1 = "0.1"
version2 = "1.1"
assert s.compareVersion(version1, version2) == -1
version1 = "1.0.1"
version2 = "1"
assert s.compareVersion(version1, version2) == 1
version1 = "7.5.2.4"
version2 = "7.5.3"
assert s.compareVersion(version1, version2) ==-1
version1 = "1.01"
version2 = "1.001"
assert s.compareVersion(version1, version2) == 0
version1 = "1.0"
version2 = "1.0.0"
assert s.compareVersion(version1, version2) == 0

class Solution4(object):
    """
    Time: O(N)
    Space: O(N)
    """
    def compareVersion(self, version1, version2):
        """
        :type version1: str
        :type version2: str
        :rtype: int
        """
        main1, _, rest1 = ('0' + version1).partition('.')
        main2, _, rest2 = ('0' + version2).partition('.')
        return (int(main1) > int(main2)) - (int(main1) < int(main2)) or len(rest1 + rest2) and self.compareVersion(rest1, rest2)

s = Solution4()
version1 = "0.1"
version2 = "1.1"
assert s.compareVersion(version1, version2) == -1
version1 = "1.0.1"
version2 = "1"
assert s.compareVersion(version1, version2) == 1
version1 = "7.5.2.4"
version2 = "7.5.3"
assert s.compareVersion(version1, version2) ==-1
version1 = "1.01"
version2 = "1.001"
assert s.compareVersion(version1, version2) == 0
version1 = "1.0"
version2 = "1.0.0"
assert s.compareVersion(version1, version2) == 0

See also:

https://leetcode.com/problems/compare-version-numbers

https://www.lintcode.com/problem/compare-version-numbers/description